﻿using UnityEngine;
using System.Collections.Generic;

namespace JH
{
    /// <summary>
    /// LTTB（Largest Triangle Three Buckets）降采样算法
    /// </summary>
    public static class LttbUtility
    {
        /// <summary>
        /// LTTB（Largest Triangle Three Buckets）降采样
        /// </summary>
        /// <param name="origin">原始数据点集（必须有序，通常按X递增）</param>
        /// <param name="threshold">目标采样点数（>=3 且 小于 origin.Count，否则直接返回原始）</param>
        /// <param name="result">采样结果将写入此集合（会先Clear）</param>
        public static void LttbDownSample(
            IReadOnlyList<Vector2> origin, int threshold, List<Vector2> result)
        {
            int n = origin.Count;

            // 1. 检查参数合法性，如果目标点数过多或过少，直接返回原始数据
            if (threshold >= n || threshold < 3)
            {
                result.Clear();
                result.AddRange(origin);
                return;
            }

            result.Clear(); // 保证结果是空的

            // 2. 计算每个bucket的大小（去掉首尾点后，剩下的点均分到 threshold-2 个bucket）
            float bucketSize = (n - 2f) / (threshold - 2); // 用float避免误差

            // 3. 保留第一个点
            result.Add(origin[0]);
            int a = 0; // 上一个被选中点的下标

            // 4. 逐个bucket处理
            for (int i = 0; i < threshold - 2; i++)
            {
                // 4.1 计算下一个bucket的平均点（用于三角面积计算）
                int rangeStart = (int)Mathf.Floor((i + 1) * bucketSize) + 1;
                int rangeEnd = (int)Mathf.Floor((i + 2) * bucketSize) + 1;
                if (rangeEnd >= n) rangeEnd = n;

                float avgX = 0f, avgY = 0f;
                int avgRange = rangeEnd - rangeStart;
                for (int j = rangeStart; j < rangeEnd; j++)
                {
                    avgX += origin[j].x;
                    avgY += origin[j].y;
                }

                if (avgRange > 0)
                {
                    avgX /= avgRange;
                    avgY /= avgRange;
                }
                else if (rangeStart - 1 < n)
                {
                    // 如果没有可用的平均点，则用前一个
                    avgX = origin[rangeStart - 1].x;
                    avgY = origin[rangeStart - 1].y;
                }

                // 4.2 在当前bucket内，寻找与a点、avg点组成三角形面积最大的那个点
                int bucketStart = (int)Mathf.Floor(i * bucketSize) + 1;
                int bucketEnd = (int)Mathf.Floor((i + 1) * bucketSize) + 1;
                if (bucketEnd >= n) bucketEnd = n - 1; // 不包含最后一个点

                float maxArea = -1f;
                int maxAreaIndex = bucketStart;

                for (int j = bucketStart; j < bucketEnd; j++)
                {
                    // 三角形面积公式（叉积法），忽略0.5，因为只比大小
                    float area = Mathf.Abs(
                        (origin[a].x - avgX) * (origin[j].y - origin[a].y) -
                        (origin[a].x - origin[j].x) * (avgY - origin[a].y)
                    );
                    if (area > maxArea)
                    {
                        maxArea = area;
                        maxAreaIndex = j;
                    }
                }

                // 4.3 选中的点加入结果
                result.Add(origin[maxAreaIndex]);

                // 4.4 更新a为刚选中的点
                a = maxAreaIndex;
            }

            // 5. 保留最后一个点
            result.Add(origin[n - 1]);
        }
    }
}